A portion of the disclosure of this patent document contains material that is subject to copyright protection. This patent document may show and/or describe matter that is or may become trade dress of the owner. The copyright and trade dress owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright and trade dress rights whatsoever.
1. Field of the Invention
The present invention relates generally to electronic data storage and retrieval. More particularly, the present invention relates to indexing technology including creation, organization, maintenance, and use of search indexes to accomplish the desired searching and data retrieval.
2. Description of Related Art
Electronic data/document storage and retrieval applications are relatively common. In fact, the Internet revolution has resulted in incredibly huge amounts of data being stored and retrieved using various application software, including database software, search engines and browsers. Despite the incredible increase in the amount of data available, as technology advances consumers are continuing to demand increasingly speedy access to that data.
Many factors have contributed to the industry""s success at delivering increased access speed to data. For example, technological advances have been realized with higher capacity and smaller physical storage devices, faster communications technologies, various system software algorithms involving caching, cookies, data compression, multiple buffering, etc., and advanced application software algorithms involving data storage and retrieval.
However, data transfer rates between a computer memory and other devices such as a display monitor, a printer, or another storage device, are still limited due to physical I/O requirements. For example, there is a huge disparity in the speeds of I/O versus the speeds of executing instructions in memory, and this disparity affects data searching and sorting. Searching for data commonly requires multiple disk seek operations, wherein the read heads of the disk readers must be physically positioned to the proper sector of the disk to read the required data. This is true even if the searched data is already sorted, and such disk seek and read operations are extremely time consuming relative to any substantive operations performed on the desired data in a computer memory.
Additionally, the Internet revolution has led to widespread use of open data formats such as HTML and to a lesser extent currently, XML, and these data formats are widely used to present information to end-users. Nonetheless, many computer applications typically create the desired presentation pages dynamically only after retrieving the desired data to occupy the pages. Some computer applications use templates that require insertion of only certain data dynamically, whereas other computer applications dynamically create entire HTML pages for presentation. In either case, the overall data presentation time for end-users is affected. Thus, systems and methods are desirable for storing, retrieving, and displaying data in a widely-accepted open data format such as HTML, wherein the I/O involved in locating desired data is reduced and the presentation time to the end user is also reduced.
The present invention provides systems and methods for data storage and retrieval in which data is stored in records within a file storage system, and desired records are identified and/or selected by conducting searches of index files which map search criteria into the appropriate records.
In accordance with the invention, an index file includes a header with header entries and a body with body entries. At least one header entry has a header-to-body pointer associated therewith that points to a body entry. The body entry pointed to is the first body entry in a set of body entries that are related to the header-to-body pointer pointing thereto. The body entries in turn comprise body-to-record-pointers that point to the desired records within a file storage system. Various index files are used to map various search criteria to the desired records.
According to one aspect of the present invention, an end-user submits a search query to a software system. The query specifies desired search criteria, and is intended to identify records satisfying the search criteria. The proper index file to be searched is identified based upon the search criteria. The desired file storage system records are then identified by locating the proper header entry within the identified index file, following the header-to-body pointer associated therewith to a corresponding body entry which is the first in a set of body entries related to the header-to-body pointer pointing thereto, and processing the set of body entries to identify and select those in the set which comprise the body-to-record pointers pointing to the desired records within the file storage system. The records pointed to by the selected body-to-record pointers are then identified as the records satisfying the search criteria, and are presented to the end-user.
In another aspect of the present invention, a record comprises a master document stored in a file system. Optional view documents are associated therewith, which enable a file storage system end-user to view the data associated with the master document in various styles, sizes, formats, and quantities.
In another aspect of the present invention, the body-to-record-pointers include volume identifiers and record identifiers associated therewith, wherein the combination of a volume identifier and a record identifier is sufficient to identify a particular record within the file storage system.
In another aspect of the present invention, a pair of index files is used cooperatively to identify and/or select the desired records in response to specific search criteria, wherein the first index file comprises body entries having body-to-body pointers pointing to the body of the second index file, and the second index file comprises body entries having body-to-record pointers.
In another aspect of the present invention, the master documents, view documents, and index files are stored in a widely accepted data format, such as HTML or XML.